/**
 * 给定一个二叉树，找出其最小深度。
 * <p>
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 * <p>
 * 说明：叶子节点是指没有子节点的节点。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：2
 * <p>
 * <p>
 * 示例 2：
 * <p>
 * <p>
 * 输入：root = [2,null,3,null,4,null,5,null,6]
 * 输出：5
 * <p>
 * <p>
 * <p>
 * <p>
 * 提示：
 * <p>
 * <p>
 * 树中节点数的范围在 [0, 10⁵] 内
 * -1000 <= Node.val <= 1000
 * <p>
 * <p>
 * Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 1268 👎 0
 */

//leetcode submit region begin(Prohibit modification and deletion)

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {

    public int minDepth(TreeNode root) {
        if (root == null)
            return 0;
        Deque<TreeNode> nodeStack = new ArrayDeque<>();
        Deque<Integer> depthStack = new ArrayDeque<>();
        int minDepth = Integer.MAX_VALUE;
        nodeStack.push(root);
        depthStack.push(1);

        while (!nodeStack.isEmpty()) {
            TreeNode node = nodeStack.pop();
            int currentDepth = depthStack.pop();

            // 检查当前节点是否为叶子节点
            if (node.left == null && node.right == null) {
                minDepth = Math.min(minDepth, currentDepth);
            } else {
                // 先压右子节点，再压左子节点，确保左子节点先被处理
                if (node.right != null && currentDepth + 1 < minDepth) {
                    nodeStack.push(node.right);
                    depthStack.push(currentDepth + 1);
                }
                if (node.left != null && currentDepth + 1 < minDepth) {
                    nodeStack.push(node.left);
                    depthStack.push(currentDepth + 1);
                }
            }
        }
        return minDepth;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
